#include <stdlib.h>
#include <stdio.h>
#include "main.h"


void _recur_create_tree(BiTreeNode * root_p, char * pre_order_seq, int * current_index_p, int num_elements){
    if (*current_index_p >= num_elements) {
        return;
    }

    root_p->data = pre_order_seq[*current_index_p];
    (*current_index_p)++;

    if (pre_order_seq[*current_index_p] == '#') {
        root_p->leftChild = NULL;
        (*current_index_p)++;
    } else {
        root_p->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _recur_create_tree(root_p->leftChild, pre_order_seq, current_index_p, num_elements);
    }
     if (pre_order_seq[*current_index_p] == '#') {
        root_p->rightChild = NULL;
        (*current_index_p)++;
    } else {
        root_p->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _recur_create_tree(root_p->rightChild, pre_order_seq, current_index_p, num_elements);
    }
}


void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements) {
    *root_pp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    int current_index = 0;
    _recur_create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}


// 递归地销毁由*root指向根节点的树：释放该树所被动态分配的内存空间
void Destroy(BiTreeNode **root)
{
    if(*root!=NULL)
    {
        Destroy(&((*root)->leftChild));
        Destroy(&((*root)->rightChild));
        free(*root);
        *root=NULL;
    }
}


//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL)
    {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)){
     if(t!=NULL)
    {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t!=NULL)
    {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

// 请实现此函数
// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode *Search(BiTreeNode *root, DataType x)
{
    BiTreeNode *find=NULL;
    return find;
}

void Visit(DataType item)
{
    printf("%c ", item);
}

int main(void)
{
  BiTreeNode *root, *p, *pp,*find;

  char * pre_order_seq = "ABC##DE#G##F###";
  create_tree(&root, pre_order_seq, 15);

  pre_order_traverse(root, Visit); // 输出应该为(不含双引号): "A B C D E G F "
  printf("\n");
  in_order_traverse(root, Visit); // 输出应该为(不含双引号): "C B E G D F A "
  printf("\n");
  post_order_traverse(root, Visit); // 输出应该为 (不含双引号): "C G E F D B A "

  char x='E';
  find=Search(root,x);
  if(find!=NULL)
    printf("\n数据元素%c在二叉树中 \n",x);
  else
    printf("\n数据元素%c不在二叉树中 \n",x);

  x = 'H';
  find=Search(root,x);
  if(find!=NULL)
    printf("\n数据元素%c在二叉树中 \n",x);
  else
    printf("\n数据元素%c不在二叉树中 \n",x);

  Destroy(&root);

}